package Solutions;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.TreeMap;

/**
 * @Classname IsSameTree
 * @Description TODO
 * @Date 2021/6/18 14:53
 * @Created by ASUS
 */
public class IsSameTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static void preorder(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> preList = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                preList.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            while (cur == null && !stack.isEmpty()) {
                cur = stack.pop().right;
            }
        }
        System.out.println(preList);
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     *
     * 添加备注
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
     * 内存消耗：35.6 MB, 在所有 Java 提交中击败了83.76% 的用户
     */
    private static byte stop;

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null && q != null) {
            stop = 1;
            return false;
        }
        if (p != null && q == null) {
            stop = 1;
            return false;
        }
        if (p != null && q != null) {
            if (p.val != q.val) stop = 1;
            else stop = 0;
            if (stop == 1) return false;
            isSameTree(p.left, q.left);
            if (stop == 1) return false;
            isSameTree(p.right, q.right);
            if (stop == 1) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, null, null), null);
        TreeNode root1 = new TreeNode(1, null, new TreeNode(2, null, null));
        System.out.println(new IsSameTree().isSameTree(root, root1));
        preorder(root);
    }

    public int dfs(TreeNode root) {
        if (root.right == null && root.left == null) return root.val;
        int res = 0;
        if (root.left != null) res += dfs(root.left);
        if (root.right != null) {
            if (!(root.right.left == null && root.right.right == null)) {
                res += dfs(root.right);
            }
        }
        return res;
    }
    public int sumOfLeftLeaves(TreeNode root) {
        if (root.right == null && root.left == null) return 0;
        return dfs(root);
    }
}
